75. 颜色分类

75. 颜色分类

题目

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1:

1
2
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

示例 2:

1
2
输入:nums = [2,0,1]
输出:[0,1,2]

示例 3:

1
2
输入:nums = [0]
输出:[0]

示例 4:

1
2
输入:nums = [1]
输出:[1]

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶:

  • 你可以不使用代码库中的排序函数来解决这道题吗?
  • 你能想出一个仅使用常数空间的一趟扫描算法吗?

注意要点

题目要求有原地排序、禁止使用排序函数以及常数空间一边扫描等要求。所以我们可以排除sort函数、hash、新数组等方法。而一边扫描最常用的就是双指针或多指针。

这道题是“荷兰国旗问题”。又是Dijkstra提的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
// p0用来交换0 p1用来交换1
int p0 = 0, p1 = 0;
for (int i = 0; i < n; ++i) {
// 如果遍历到的数为1
if (nums[i] == 1) {
// 和p1交换,p1++
swap(nums[i], nums[p1]);
++p1;
// 如果遍历到的数为0
} else if (nums[i] == 0) {
// 交换p0
swap(nums[i], nums[p0]);
// 如果此时p0在p1前面,说明此时1被交换到了外面,所以需要再交换到p1的位置
if (p0 < p1) {
swap(nums[i], nums[p1]);
}
// 都要自增
++p0;
// 如果p0<p1,因为做了交换,所以要自增
// 如果p1<=p0。显然该位置放了0 所以p1也要自增
++p1;
}
}
}
};